#include <iostream>
using namespace std;

int A[3][3];      // 填入方阵
bool used[10];    // 控制1-10每个数用一次
int countNum = 0; // 计数

int PrimeTable[8] = {2, 3, 5, 7, 11, 13, 17, 19};

void print()
{
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
            cout << A[i][j] << " ";
        cout << endl;
    }
    cout << endl;
}

// 1-10相邻数之和不超过20，查表法判断质数
bool isPrime(int num)
{
    for (int i = 0; i < 8; i++)
        if (PrimeTable[i] == num)
            return true;
    return false;
}

// 查看在(x,y)填入num后，检查相邻数是否为质数
bool Neighbor(int x, int y, int num)
{
    // 没有必要判断四个方向，因为我们填入是有顺序的
    if (x - 1 >= 0 && !isPrime(A[x - 1][y] + num))
        return false;
    if (y - 1 >= 0 && !isPrime(A[x][y - 1] + num))
        return false;
    return true;
}

// dfs思路，从(0,0)出发，先向右，再向下
// (x,y) 当前坐标
void fill(int x, int y)
{
    if (x == 3)
        // print();
        countNum++;
    else
    {
        for (int i = 1; i <= 10; i++)
        {
            if (!used[i - 1] && Neighbor(x, y, i))
            {
                A[x][y] = i, used[i - 1] = true; // 赋值，进入一次dfs
                if (y == 2)
                    fill(x + 1, 0);
                else
                    fill(x, y + 1);
                A[x][y] = 0, used[i - 1] = false; // 重置，试下一个值
            }
        }
    }
}

int main()
{
    memset(A, 0, 9);
    memset(used, false, 10);
    fill(0, 0);
    cout << "总共有" << countNum << "种填入方式" << endl; // 128
    return 0;
}